package com.lwl.shua.class01;

import com.lwl.Utils.PrintUtil;

/**
 * @author lwl
 * @Description TODO
 * @date 2025/9/5 18:14
 */
public class Code07Lc494FindTargetSumWays {
    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 1, 1};
        int target = 3;
        System.out.println(findTargetSumWays(nums, target));
    }

    public static int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }

        int[][] dp = new int[nums.length + 1][2 * sum + 1];
        dp[0][0] = 1;
        for (int i = nums.length - 1; i >= 0; i--) {

        }
        PrintUtil.printArray(dp);
        return dp[0][target];
    }

    public static int findTargetSumWays3(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // 如果 target 超过了数组总和的绝对值，则无解
        if (Math.abs(target) > sum) {
            return 0;
        }
        // dp[i][j] 表示前 i 个数字能够组成和为 j 的方案数
        // 因为和可能为负数，所以需要偏移量 sum，使得索引非负
        int[][] dp = new int[nums.length + 1][2 * sum + 1];
        // 初始状态：没有数字时，和为 0 的方案数为 1
        dp[0][sum] = 1;
        for (int i = 1; i <= nums.length; i++) {
            for (int j = -sum; j <= sum; j++) {
                // 加上当前数字的方案数
                if (j - nums[i - 1] >= -sum) {
                    dp[i][j + sum] += dp[i - 1][j - nums[i - 1] + sum];
                }
                // 减去当前数字的方案数
                if (j + nums[i - 1] <= sum) {
                    dp[i][j + sum] += dp[i - 1][j + nums[i - 1] + sum];
                }
            }
        }
        return dp[nums.length][target + sum];
    }

    public static int findTargetSumWays2(int[] nums, int target) {
        return process(0, nums, target);
    }

    private static int process(int curIndex, int[] nums, int rest) {
        if (curIndex == nums.length) {
            return rest == 0 ? 1 : 0;
        }
        int p1 = process(curIndex + 1, nums, rest + nums[curIndex]);
        int p2 = process(curIndex + 1, nums, rest - nums[curIndex]);
        return p1 + p2;
    }

}
